package com.south.base.test.arithmetic.dynamic.programming;

import org.junit.Assert;
import org.junit.Test;

/**
 * @author Administrator
 * @date 2019/12/25 10:00
 */
public class MaximalSquare {
    /**
     * 在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
     */
    @Test
    public void maximalSquare() {
        Assert.assertEquals(4, maximalSquare(new char[][]{{'1', '0', '1', '0', '0'}, {'1', '0', '1', '1', '1'}, {'1', '1', '1', '1', '1'}, {'1', '0', '0', '1', '0'}}));
        Assert.assertEquals(9, maximalSquare(new char[][]{{'1', '0', '1', '0', '0'}, {'1', '0', '1', '1', '1'}, {'1', '1', '1', '1', '1'}, {'1', '0', '1', '1', '1'}}));
        Assert.assertEquals(9, maximalSquare(new char[][]{{'0', '0', '0', '1'}, {'1', '1', '0', '1'}, {'1', '1', '1', '1'}, {'0', '1', '1', '1'}, {'0', '1', '1', '1'}}));
        Assert.assertEquals(4, maximalSquare2(new char[][]{{'1', '0', '1', '0', '0'}, {'1', '0', '1', '1', '1'}, {'1', '1', '1', '1', '1'}, {'1', '0', '0', '1', '0'}}));
        Assert.assertEquals(9, maximalSquare2(new char[][]{{'1', '0', '1', '0', '0'}, {'1', '0', '1', '1', '1'}, {'1', '1', '1', '1', '1'}, {'1', '0', '1', '1', '1'}}));
        Assert.assertEquals(9, maximalSquare2(new char[][]{{'0', '0', '0', '1'}, {'1', '1', '0', '1'}, {'1', '1', '1', '1'}, {'0', '1', '1', '1'}, {'0', '1', '1', '1'}}));
    }

    public int maximalSquare(char[][] matrix) {
        int res = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (isTrue(matrix[i][j])) {
                    res = res < 1 ? 1 : res;
                    for (int k = 1; k < matrix.length - i && k < matrix[0].length - j; k++) {
                        boolean f = isTrue(matrix[i + k][j + k]);
                        for (int l = 0; l < k; l++) {
                            f = f && isTrue(matrix[i + k][j + l]) && isTrue(matrix[i + l][j + k]);
                        }
                        if (f) {
                            int area = (k + 1) * (k + 1);
                            res = res < area ? area : res;
                        } else {
                            break;
                        }
                    }

                }
            }
        }
        return res;
    }

    public int maximalSquare2(char[][] matrix) {
        int rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;
        int[][] dp = new int[rows + 1][cols + 1];
        int max = 0;
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                if (isTrue(matrix[i - 1][j - 1])) {
                    dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
                    max = Math.max(max, dp[i][j]);
                }
            }
        }
        return max * max;
    }

    private boolean isTrue(char c) {
        return c == '1';
    }
}
